package leetcode.sort;

/**
 把没有排好序的第一个元素，插入到已排好序元素的合适位置
 */
public class InsertSort {
    public static void main(String[] args) {
        int [] arr = new int[]{1,3,2,5,8,5,7,4,2,10,19,13,12};
        new InsertSort().insertSort(arr);
        for (int i : arr) {
            System.out.print(i+" ");
        }
    }

    private void insertSort(int []nums){
        for (int i = 1; i < nums.length; i++) {
            for (int j = i; j >0 && nums[j]<nums[j-1] ; j--) {
                swap(nums,j,j-1);
            }
        }
    }

    private void swap(int []nums,int i,int j){
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }


}